package day01;

// 找数组中出现次数超过数组长度的数

//import java.util.HashMap;
//public class Solution {
//    public int MoreThanHalfNum_Solution(int [] array) {
//        int half = array.length / 2;
//        // 方法一：HashMap法
//        HashMap<Integer,Integer> map =  new HashMap<>();
//        for(int i=0; i<array.length; i++) {
//            if(map.get(array[i]) == null) {
//                map.put(array[i],1);
//            } else {
//                map.put(array[i],map.get(array[i])+1);
//            }
//        }
//        for(int i=0; i<array.length; i++) {
//            if(map.get(array[i]) > half) {
//                return array[i];
//            }
//        }
//        return 0;
//    }
//}



public class Main2 {
    public int MoreThanHalfNum_Solution(int [] array) {
        // 方法二：次数相消法
        int half = array.length / 2;
        int target = array[0];
        int times = 0;
        for(int i=0; i<array.length; i++) {
            if(times == 0) {
                // 更新target/times
                target = array[i];
                times = 1;
            } else if(target == array[i]) {
                times++;
            } else {
                times--;
            }
        }
        // 最后再遍历确定到底是不是大于一半（double check）
        times = 0;
        for(int i=0; i<array.length; i++) {
            if(target == array[i]) {
                times++;
            }
        }
        return (times>half)? target:0;
    }

    public static void main(String[] args) {
        int[] array = {1,1,1,1,1,1,1,1,1,3,3,3,3,3,3,3,3,3,1,3,3};
        Main2 main2 = new Main2();
        System.out.println(main2.MoreThanHalfNum_Solution(array));
    }
}
